#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#define MAX_FILE_NAME 66
#define MAX_DEPEND_FILES 105
#define MAX_FILES 1005
#define MAX_LINE_LEN 1005

typedef enum Color 
{ 
   WHITE,
   GREY, 
   BLACK
} Color;


typedef struct file_vertex 
{
	char file_name[MAX_FILE_NAME];
	int edges[MAX_DEPEND_FILES];

} file_vertex;


typedef struct vertex_auxiliary
{
	Color col;
	int last_index_adj_array;

} vertex_auxiliary;

/* this function performs a binary search of string 'filename' in a sorted array,
   and returns 'filename' index if found, and -1 otherwise.
   Also, if called with insertion_place_flag=1, it will return the correct insertion place
   of 'filename' in the array, if it doesn't exist, and -1 if it does. */
int binary_search_array (file_vertex dependencies[], int low, int high, char target[], int insertion_place_flag) 
{
	int middle=0;

    if (high < low)
	{
		if (insertion_place_flag) 
		{
			return low; /* the place where we should insert target. */

		} else {

			return -1;  /* not found (regular binary search). */
		} 
	}

    middle = (low + high)/2;

    if (strcmp(target, dependencies[middle].file_name) < 0) 
	{
		/* search in left sub-array. */
        return binary_search_array(dependencies, low, middle-1, target, insertion_place_flag); 

	} else { 

		if (strcmp(target, dependencies[middle].file_name) > 0) 
		{
			/* search in right sub-array. */
			return binary_search_array(dependencies, middle+1, high, target, insertion_place_flag); 

		} else {

			if (insertion_place_flag) /* filename already exists in array, we return negative int. */
			{
				return -1;

			} else {

				return middle;   /* index of our search query (regular binary search). */
			}
		}
	}

}


void add_filename_at_index(file_vertex dependencies[], int index, int* last_index, char filename[]) 
{
	int i=0;

	(*last_index)++;   /* updates last index. */

	for (i=*last_index; i>index; i--) 
	{
		/* moves one cell right every element at ind. greater than index. */
		strcpy(dependencies[i].file_name, dependencies[i-1].file_name);
	}

	/* inserts the new item at position 'index'. */
	strcpy(dependencies[index].file_name, filename);
}


void fill_filenames(file_vertex dependencies[], FILE* input_file, int* last_filled_index)
{
	char file_line[MAX_LINE_LEN];
	char left_file[MAX_FILE_NAME];
	char deps[MAX_LINE_LEN];
	int ind;

	char* name;

	while(1) {
			
		fgets(file_line, MAX_LINE_LEN, input_file);  /* reading a line from input file. */
        if (feof(input_file)) {   /* the last, 'empty line', was read. */
			break;
        }

		file_line[strlen(file_line)-1]='\0';
		sscanf(file_line,"%s%s",left_file,deps);

		left_file[strlen(left_file)-1]='\0';

		ind=binary_search_array(dependencies, 0, last_filled_index, left_file, 1); 

		if (ind >= 0)
		{
			add_filename_at_index(dependencies, ind, last_filled_index, left_file);
		}

		name=strtok(deps,",");

		while (name != NULL) {

			ind=binary_search_array(dependencies, 0, *last_filled_index, name, 1); 

			if (ind >= 0)
			{
				add_filename_at_index(dependencies, ind, *last_filled_index, left_file);
			}

			name=strtok(NULL,",");
		}

	 }  /* end of outer while. */


}



int main()
{

	file_vertex dependencies[MAX_FILES];
	Color DFS_vertex_color[MAX_FILES];

	char str[]="1: 2,3,4,5,6,7,8,9,10\n";
	char fn[66];
	char deps[1005];
	char* names;


	str[strlen(str)-1]='\0';

	sscanf(str,"%s%s",fn,deps);

	fn[strlen(fn)-1]='\0';

	names=strtok(deps,",");

	printf("%d\n",*(names+1));

	while (names != NULL) {

		printf("%s ",names);
		names=strtok(NULL,",");
	
	}

	getchar();

	return 0;
}